CSE 311: Section 4

Task 1 – Cartesian Products

Let $A$, $B$, $C$, and $D$ be sets. Consider the following claim: $$(A\cap B) \times C \subseteq A \times (C\cup D)$$

1. Suppose that $A = \{1,2\}$, $B = \{1,2,3\}, C = \{3,4\}, D = \{2\}$.

   Calculate the values of the sets $(A \cap B) \times C$ and $A \times (C \cup D)$. Check whether the claim holds.

2. Suppose that $A = \{1,2\}$, $B = \{2,3,4\}, C = \{1,2,3\}, D = \{1,3\}$.

   Calculate the values of the sets $(A \cap B) \times C$ and $A \times (C \cup D)$. Check whether the claim holds.

3. Write an English proof that the claim holds.

   Follow the structure of our template for subset proofs.

   Note: even though we want you to write your proof directly in English, it must still look like the translation of a formal proof. In particular, you must include all steps that would be required of a formal proof, excepting only those that we have explicitly said are okay to skip in English proofs.

Task 2 – Power Sets

Let $A$ and $B$ be sets. Consider the following claim: $$\mathop{\mathrm{\mathcal{P}}}(A) \subseteq \mathop{\mathrm{\mathcal{P}}}(B)$$

1. Suppose that $A = \{1\}$, $B = \{1, 2\}$.

   Calculate the values of the sets $\mathop{\mathrm{\mathcal{P}}}(A)$ and $\mathop{\mathrm{\mathcal{P}}}(B)$. Check whether the claim holds.

2. Suppose that $A = \{1\}$, $B = \{2, 3\}$.

   Calculate the values of the sets $\mathop{\mathrm{\mathcal{P}}}(A)$ and $\mathop{\mathrm{\mathcal{P}}}(B)$. Check whether the claim holds.

3. Write an English proof that the claim holds given that $A \subseteq B$.

   (This updated claim describes the situation in part (a) but not part (b).)

   Follow the structure of our template for subset proofs.

   Note: even though we want you to write your proof directly in English, it must still look like the translation of a formal proof. In particular, you must include all steps that would be required of a formal proof, excepting only those that we have explicitly said are okay to skip in English proofs.

Task 3 – Set Equality

Let $A$, $B$, and $C$ be sets. For each of the following claims:

1. State whether the the claim is true or false.

2. If the claim is true, write an English proof that the claim holds following the Meta Theorem template. (In your equivalence chain, you can skip steps showing commutativity or associativity, as long as each step is easy to follow.)

3. If it the claim false, give a counterexample. Provide specific finite sets for $A$, $B$, and $C$, and then calculate the value of each side of the claim, showing that they do not produce the same set. (Be sure to show the value of each intermediate expression, when calculating each side.)

1. $(A\,\setminus\,B)\,\setminus\,C = A\,\setminus\,(B \cap C)$

2. $A\,\setminus\,(B \cup C) = (A\,\setminus\,B) \cap (A\,\setminus\,C)$

Task 4 – Structural Induction on Lists

Recall the definition of lists of numbers from lecture:

Basis Step: $\mathop{\mathrm{\textsf{nil}}}\in \textbf{List}$

Recursive Step: for any $a \in \mathbb{Z}$, if $L \in \textbf{List}$, then $a :: L \in \textbf{List}$.

For example, the list $[1, 2, 3]$ would be created recursively from the empty list as $1 :: (2 :: (3 :: \mathop{\mathrm{\textsf{nil}}}))$. We will consider “$::$” to associate to the right, so $1 :: 2 :: 3 :: \mathop{\mathrm{\textsf{nil}}}$ means the same thing.

The parts below use two recursively-defined functions. The first is $\mathop{\mathrm{\textsf{len}}}$, which calculates the length of the list. It is defined recursively as follows: $$\begin{array}{rcll} \mathop{\mathrm{\textsf{len}}}(\mathop{\mathrm{\textsf{nil}}}) &:=& 0 & \\ \mathop{\mathrm{\textsf{len}}}(a :: L) &:=& 1 + \mathop{\mathrm{\textsf{len}}}(L) & \forall a \in \mathbb{Z}, \forall L \in \textbf{List} \end{array}$$

The second function, $\mathop{\mathrm{\textsf{echo-pos}}}$, which duplicates each positive number in the list, is defined by: $$\begin{array}{rclll} \mathop{\mathrm{\textsf{echo-pos}}}(\mathop{\mathrm{\textsf{nil}}}) &:=& \mathop{\mathrm{\textsf{nil}}}& \\ \mathop{\mathrm{\textsf{echo-pos}}}(a :: L) &:=& a :: \mathop{\mathrm{\textsf{echo-pos}}}(L) & \text{ if $a \le 0$} & \forall a \in \mathbb{Z}, \forall L \in \textbf{List} \\ \mathop{\mathrm{\textsf{echo-pos}}}(a :: L) &:=& a :: a :: \mathop{\mathrm{\textsf{echo-pos}}}(L) & \text{ if $a > 0$} & \forall a \in \mathbb{Z}, \forall L \in \textbf{List} \end{array}$$ For example, with these definitions, we get $\mathop{\mathrm{\textsf{echo-pos}}}(-1 :: 2 :: -3 :: \mathop{\mathrm{\textsf{nil}}}) = -1 :: 2 :: 2 :: -3 :: \mathop{\mathrm{\textsf{nil}}}$.

1. Write a calculation block, citing the appropriate definitions, showing that $$\mathop{\mathrm{\textsf{echo-pos}}}(1 :: -2 :: 3 :: \mathop{\mathrm{\textsf{nil}}}) = 1 :: 1 :: -2 :: 3 :: 3 :: \mathop{\mathrm{\textsf{nil}}}$$

2. Use structural induction to prove that $$\forall L \in \textbf{List}\,(\mathop{\mathrm{\textsf{len}}}(\mathop{\mathrm{\textsf{echo-pos}}}(L)) \le 2 \mathop{\mathrm{\textsf{len}}}(L))$$ Hint: Use cases in the inductive step.